1. Field of the Invention
The present invention relates generally to creating three-dimensional (3D) geometry from two-dimensional (2D) line data, and in particular, to a method, apparatus, and article of manufacture for transitioning between two different profile curves during a swept surface extrusion operation used to create 3D geometry.
2. Description of the Related Art
Swept surface extrusion is a well-known operation for generating 3D objects from line data. It uses a, usually 2D, profile curve that is conceptually moved along lines to form 3D geometry. The profile curve is oriented orthogonally relative to the respective line. In many situations, the profile curve may vary during the extrusion. For example, the curve may transition from one profile curve (having a first number of points) to another profile curve (having a second number of points) during the sweep operation. Prior art methods fail to automatically and efficiently transition between two profile curves that have different numbers of points. Instead, prior art methods transition using linear interpolation and/or require a manual configuration and interpolation configuration. Such problems may be better understood with a description of prior art 3D creation and profile extrusion transitions.
There is abundant prior art in the field of swept surface extrusion. This includes surfaces of revolution as well as extrusions along (not necessarily straight) lines. In the context of the present invention, the focus is on extrusions along lines with the goal of computing triangles (for a 3D mesh) and the attributes of the resulting surface.
An exemplary use case in the context of the present invention is that of the generation of road geometry from a road network. The geometry is derived using an attributed profile curve with attributes, such as normal, texture, and purpose. The attributes are assigned to sections of the profile curve and can be used, e.g., for controlling the visual appearance of the resulting road. When the style changes within a road or at road connections, a suitable transition needs to be generated. For example, driving lanes in both styles need to be seamlessly connected in order to enable travelling cars. FIG. 1 illustrates an example transition between two road styles. Each road style 102 and 104 is represented by an attributed profile curve. Methods must be able to identify and connect matching profile curve sections (such as roadway, bikeway, and sidewalk). In the example of FIG. 1, the curb 106 between bikeway 108 and roadway 110 (in the undivided road 102) fades out while a new curb 112 between bikeway 108 and green-space 114 fades in (in the divided road 104).
The prior art fails to provide the ability to create a smooth transition from the undivided road 102 to the divided road 104 in an automated fashion. Such a transition is also known in the prior art as morphing. Morphing is a common technique for transitioning between two different profile curves in swept surface extrusion. Morphing interpolates vertex coordinates of one profile curve along the transition such that it becomes identical to the other profile curve. For road styles, this approach cannot guarantee a suitable transition that enables a seamless transition.
In the context of 3D geometry, morphing transforms geometric representations. Typically, morphing denotes the smooth transformation of one 3D object's geometry into another 3D object's geometry. A frequent usage is the blending of key frame geometry for animation. There exists a large number of morphing techniques, optimized for various use cases and focusing on certain properties of the objects. For example, morphing can preserve volume, minimize curvature or texture distortion, consider appearance information, or prevent self-intersections. Also, changes in topology can be handled differently. With respect to geo-data in street networks, the focus is on one-to-one vertex position morphing. Such an approach requires both objects to contain the same number of vertices in the same topology. Then, the morphed object can be formed by using the common topology and interpolating the positions of corresponding vertices in both objects. Correspondence can be simply defined by an identical vertex number. The interpolation can employ any desired function, typically linear or smoothstep interpolation.
Some prior art techniques may apply a profile curve morphing within a transition zone. However, the prior art employs a simple priority-based profile curve matching and thus fails to find an optimal section matching. Alternative prior art techniques provide corridors as a means for generating roads. Such corridors are generated from an alignment (2D centerline), a profile (elevation of the centerline), and an assembly (profile curve). An assembly consists of subassemblies representing different road sections such as roadway, curb, or sidewalk. While the prior art may provide large freedom for assemblies along an alignment, there is no matching of similar sections/categories (e.g., roadway, curb, sidewalk, etc.). Instead, the prior art relies on the user to fine tune transitions using respective subassemblies. In yet another prior art system, objects extrude arbitrary cross sections along a path using generic morphing between cross sections. However, cross sections need to have identical vertex count for morphing—a matching of some sort is not applied. Similar extrusion objects or swept surface objects may be available in various 3D content creation tools.
While morphing contains some building blocks for enabling a smooth transition (e.g., adjusting matching sections, or inserting collapsed sections), using a string edit distance for matching may improve results. String edit distances can be used to compare two strings, typically genome or protein sequences, through the use of string manipulations (e.g., character insertion, deletion, or substitution). Two strings are considered more similar the fewer manipulations it takes to convert one into the other. A well-known string edit distance is the Levenshtein distance, which weights all manipulations equally. Other string edit distances differ in the allowed manipulations and weighting schemes.
Consequently, as described above, the prior art fails to provide an efficient and simple mechanism for morphing/transitioning between two profile curves on a road/street network. Thus, what is needed is the ability to enable sound, automatic, and smooth transitions between arbitrary attributed profile curves. Such a capability that is well suited for processing large road networks with only small user interaction is also desirable.